/* 继承二叉搜索树 */

import { BinarySearchTree as BSTree } from "./00_二叉搜索树";
import { AVLTreeNode } from "./03_AVL树节点封装_左旋转";

class AVLTree<T> extends BSTree<T> {
  //覆盖父类方法
  protected createNode(value: T): AVLTreeNode<T> {
    return new AVLTreeNode(value);
  }

  //覆盖父类的检查节点是否平衡
  protected checkBalancedNode(node: AVLTreeNode<T>): void {
    let current = node.parent;
    while (current) {
      if (!current.isBalanced) {
        this.rebalanced(current);
      }
      current = current.parent;
    }
  }

  /**
   * 根据不平衡的节点的情况（LL/RR/LR/RL）让子树平衡
   * @param root 找到的不平衡点
   */
  rebalanced(root: AVLTreeNode<T>) {
    const pivot = root.higherChild;
    const current = pivot?.higherChild;

    let resultNode: AVLTreeNode<T> | null = null;

    if (pivot?.isLeft) {
      //L
      if (current?.isLeft) {
        resultNode = root.rightRotation();
      } else {
        //R
        pivot.leftRotation();
        resultNode = root.rightRotation();
      }
    } else {
      //R
      if (current?.isLeft) {
        //L
        pivot?.rightRotation();
        resultNode = root.leftRotation();
      } else {
        //R
        resultNode = root.leftRotation();
      }
    }

    if (!resultNode?.parent) {
      this.root = resultNode;
    }
  }
}

const avlTree = new AVLTree<number>();

let arr: number[] = [];
let anc: number[] = [];
for (let i = 0; i <= 10; i++) {
  const value = Math.floor(Math.random() * 200);
  anc.push(value);
  if (i % 2 === 0 && arr.length < 5) {
    arr.push(value);
  }

  avlTree.insert(value);
}

avlTree.print();
console.log(anc, arr, "arr");

for (const k of arr) {
  avlTree.remove(k);
}

avlTree.print();
